Quicksort


How does Quicksort work?

	if size of array is 0 or 1, return
	select any item in array as the pivot
	put values smaller than pivot into group L
	put values larger than pivot into group R
	recursively sort L and R
	return L followed by pivot followed by R

	divide and conquer
	fastest known comparison-based sorting algorithm


Show each step of Quicksort on the array.

	8 5 4 6 2 3 1

	choose pivot 4 (a lucky choice)
	partition into 2 3 1 and 8 5 6
	quicksort 2 3 1
	    choose pivot 2
	    partition into 1 and 3
	    quicksort 1
	        return 1
	    quicksort 3
	        return 3
	    return 1 2 3
	quicksort 8 5 6
	    choose pivot 6
	    partition into 5 and 8
	    quicksort 5
	        return 5
	    quicksort 8
	        return 8
	    return 5 6 8
	return 1 2 3 4 5 6 8


    void quicksort( Comparable [ ] a ) {
        quicksort( a, 0, a.length - 1 );
    }
    void quicksort( Comparable [ ] a, int low, int high ) {
        if( low < high ) {
	    int pivot = partition(a, low, high);
            quicksort( a, low, pivot - 1 );
            quicksort( a, pivot + 1, high );
        }
    }
    int partition (Comparable[] a, int low, int high) {
        Comparable pivot = a[low];
        int i = low;
	int j = high+1;
	while (i < j) {
	    do i++; while(i < j && a[ i ].compareTo( pivot ) < 0 );
	    do j--; while(i <= j && a[ j ].compareTo( pivot ) > 0 );
	    if (i < j) {
	        Comparable temp = a[i];
		a[i] = a[j];
		a[j] = temp;
            }
	}
	a[low] = a[j];
	a[j] = pivot;
	return j;
    }



Can you prove QuickSort works?

	assume recursive call sorts the items smaller than the pivot
	assume recursive call sorts the items larger than the pivot
	the pivot falls between the smaller and larger items


DEMO	(quicksort running time on sorted, reverse, random data)



What's the major disadvantage of Mergesort?
Does Quicksort have this problem?

	mergesort requires an extra array
	quicksort partitions in-place, doesn't need extra array


Why is Quicksort faster than Mergesort?

	partition faster than merge
	less copying of data


What's the Big-Oh bound for the partition step?

	O(n)



The result of partitioning greatly affects Quicksort running time.



What's the Best-Case partitioning for Quicksort?

	partition gives two equal-size sets
	recursively solve two half-size problems
	happens at every step


What's the running time formula for Quicksort in the Best-Case?

	T(n) = a*n + 2*T(n/2)


What's the Big-Oh for Quicksort in the Best-Case?

	same formula as Mergesort
	O(N log N)



What's the Worst-Case partitioning for Quicksort?

	partition gives one empty partition, other size N-1
	recursively solve size N-1 problem
	happens at every step


What's the running time formula for Quicksort in the Worst-Case?

	T(n) = a*n + T(n-1)
	T(1) = b


What's the Big-Oh for Quicksort in the Worst-Case?

	T(1) = b
	T(2) = 2a + b
	T(3) = 3a + 2a + b
	T(4) = 4a + 3a + 2a + b
	T(5) = 5a + 4a + 3a + 2a + b

	T(n) = n(n+1)/2 - 1

	O(N^2)



What's the Average-Case partitioning for Quicksort?

	all possible partitions are equally likely at every step


What's the running time formula for Quicksort in the Average-Case?

	a bit complicated
	see the textbook


What's the Big-Oh for Quicksort in the Average-Case?

	O(N log N)



What determines whether Quicksort runs in O(n log n) or O(n^2) time?

	[The choice of the pivot value]


What's the outcome of using the first item as Pivot?
(This is a popular choice.)

	quadratic time on sorted/reverse data
	never choose the first item


What's the outcome of using the middle item as Pivot?

	works well on sorted/reverse data
	a reasonable choice
	some inputs can still result in quadratic time


What's the median of a list of numbers?

	median is middle number in a sorted list


Why not select the median value from the array as Pivot?
(This would always give perfect partitioning.)

	takes too long to compute the median


How can you estimate the median without spending too much time?

	sampling
	Median-of-three
	use median of first, middle, last as pivot


Compute the Median-of-three for the list of numbers.

	8 2 4 1 2 4